/*
 * @lc app=leetcode.cn id=393 lang=cpp
 *
 * [393] UTF-8 编码验证
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int n = data.size();
        for (int i = 0; i < n; ) {
            int t = data[i];
            int j = 7;
            //遍历找每个字符第一个0出现的位置
            while (j >= 0 && (((t >> j) & 1) == 1)) {
                j--;
            } 
            //从第7位往后1的个数
            int cnt = 7 - j;
            if (cnt == 1 || cnt > 4) {
                return false;
            } 
            if (i + cnt - 1 >= n) {
                return false;
            } 
            //向后检查第8位和第7位是否为10
            for (int k = i + 1; k < i + cnt; k++) {
                if ((((data[k] >> 7) & 1) == 1) && (((data[k] >> 6) & 1) == 0)) {
                    continue;
                } 
                return false;
            }
            if (cnt == 0) {
                i++;
            }else {
                i += cnt;
            } 
        }
        return true;
    }
};
// @lc code=end

